{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "## 第9章-EM算法及推广-EM算法的导出\n",
    "\n",
    "&emsp;&emsp;EM算法本质上是估计一个密度函数，在估计密度函数时，通过观测值采用最大化似然函数估计参数$\\theta$。EM算法针对的是含有隐变量的密度函数的估计问题，这个时候直接最大化似然函数会比较困难，借鉴的算法思路和第6章改进的迭代尺度法是类似的，通过不等式放缩，将最大化观测数据的对数似然函数转化为另外一个比较好实现的式子，在推导EM算法时，与书上的数学符号保持一致。  \n",
    "&emsp;&emsp;首先有一个需要观测的向量$\\theta$，观测数据$Y=(y_1,y_2,\\cdots,y_N)$，隐变量$Z=(z_1,z_2,\\cdots,z_N)$，当求解$\\theta$时，似然函数为$$\\begin{aligned} L(\\theta)\n",
    "&= \\ln P(Y|\\theta) \\\\\n",
    "&= \\ln \\sum_Z P(Y,Z|\\theta) \\\\\n",
    "&= \\ln \\left( \\sum_Z P(Z|\\theta) P(Y|Z,\\theta) \\right)\n",
    "\\end{aligned}$$&emsp;&emsp;假设在第$i$次迭代后$\\theta$的估计值为$\\theta^{(i)}$，希望新估计值$\\theta$能使$L(\\theta)$增加，即$L(\\theta) > L(\\theta^{(i)})$，则可计算两者的差：  \n",
    "$$L(\\theta)-L(\\theta^{(i)}) \n",
    "= \\ln \\left( \\sum_Z P(Z|\\theta) P(Y|Z,\\theta) \\right) - \\ln P(Y|\\theta^{(i)})$$  \n",
    "&emsp;&emsp;一般来说，对$\\ln P_1 P_2 \\cdots P_N$比较好处理，但是如果是$\\ln \\sum P_1 P_2$就不好处理，为了将$\\sum$求和符号去掉，用Jenson不等式进行缩放处理。 \n",
    "\n",
    "> **Jenson不等式：** $$f(\\sum_i \\alpha_i x_i) \\geqslant \\sum_i \\alpha_i f(x_i)$$其中函数$f$是凸函数，那么对数函数也是凸函数，$\\displaystyle \\sum_i \\alpha_i = 1$，$\\alpha_i$表示权值，$0 \\leqslant \\alpha_i \\leqslant 1$\n",
    "\n",
    "&emsp;&emsp;对于上述形式，对$Z$求和，要如何凑出来一个具有Jenson不等式中的$\\alpha_i$呢？很容易想到，关于$Z$的密度函数，该密度函数取值求和为1，需要构造一个$Z$的概率分布。  \n",
    "$\\begin{aligned}L(\\theta)-L(\\theta^{(i)}) \n",
    "=& \\ln \\left( \\sum_Z P(Z|\\theta) P(Y|Z,\\theta) \\right) - \\ln P(Y|\\theta^{(i)}) \\\\\n",
    "=& \\ln \\left( \\sum_Z P(Z|Y,\\theta^{(i)}) \\frac{P(Z|\\theta)P(Y|Z,\\theta)}{P(Z|Y,\\theta^{(i)})}  \\right) - \\ln P(Y|\\theta^{(i)}) \n",
    "\\end{aligned}$  \n",
    "利用Jesson不等式，$\\displaystyle \\ln \\left( \\sum_Z P(Z|Y,\\theta^{(i)}) \\frac{P(Z|\\theta)P(Y|Z,\\theta)}{P(Z|Y,\\theta^{(i)})}  \\right) \\geqslant \\sum_Z P(Z|Y,\\theta^{(i)}) \\ln \\frac{P(Z|\\theta)P(Y|Z,\\theta)}{P(Z|Y,\\theta^{(i)})}$  \n",
    "$\\displaystyle \\because \\ln P(Y|\\theta^{(i)}) = \\sum_Z P(Z|Y,\\theta^{(i)}) \\ln P(Y|\\theta^{(i)})$  \n",
    "$\\begin{aligned} \\therefore L(\\theta)-L(\\theta^{(i)}) \n",
    "& \\geqslant \\sum_Z P(Z|Y,\\theta^{(i)}) \\ln \\frac{P(Z|\\theta)P(Y|Z,\\theta)}{P(Z|Y,\\theta^{(i)})} - \\sum_Z P(Z|Y,\\theta^{(i)}) \\ln P(Y|\\theta^{(i)}) \\\\\n",
    "&= \\sum_Z P(Z|Y,\\theta^{(i)}) \\ln \\frac{P(Z|\\theta)P(Y|Z,\\theta)}{P(Z|Y,\\theta^{(i)}) P(Y|\\theta^{(i)})}\n",
    "\\end{aligned}$  \n",
    "令$\\displaystyle B(\\theta,\\theta^{(i)}) = L(\\theta^{(i)}) + \\sum_Z P(Z|Y,\\theta^{(i)}) \\ln \\frac{P(Z|\\theta)P(Y|Z,\\theta)}{P(Z|Y,\\theta^{(i)}) P(Y|\\theta^{(i)})} $  \n",
    "$\\therefore L(\\theta) \\geqslant B(\\theta,\\theta^{(i)})$，也就是说$B(\\theta,\\theta^{(i)})$是$L(\\theta)$的一个下界，要最大化$L(\\theta)$，可换成最大化$B(\\theta,\\theta^{(i)})$，这个和之前的改进的迭代尺度法的思路是一致的。  \n",
    "$\\begin{aligned} \\therefore \\theta^{(i+1)} \n",
    "=& \\mathop{\\arg \\max} \\limits_{\\theta} B(\\theta,\\theta^{(i)})  \\\\\n",
    "=& \\mathop{\\arg \\max} \\limits_{\\theta} \\left( \\sum_Z P(Z|Y,\\theta^{(i)}) \\ln P(Z|\\theta)P(Y|Z,\\theta) \\right) \\\\\n",
    "=& \\mathop{\\arg \\max} \\limits_{\\theta} \\left( \\sum_Z P(Z|Y,\\theta^{(i)}) \\ln P(Y,Z|\\theta) \\right) \n",
    "\\end{aligned}$  \n",
    "$\\displaystyle \\because Q(\\theta, \\theta^{(i)}) = \\sum_Z \\ln P(Y,Z|\\theta) P(Z|Y,\\theta^{(i)}) $  \n",
    "$\\displaystyle \\therefore \\theta^{(i+1)} = \\mathop{\\arg \\max} \\limits_{\\theta} Q(\\theta, \\theta^{(i)})$  \n",
    "&emsp;&emsp;等价于EM算法的M步，E步等价于求$\\displaystyle \\sum_Z P(Z|Y,\\theta^{(i)}) \\ln P(Y,Z|\\theta)$，以上就得到了EM算法，通过不断求解下界的极大化逼近求解对数似然函数极大化。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.2"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Table of Contents",
   "title_sidebar": "Contents",
   "toc_cell": false,
   "toc_position": {},
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
